package com.example.demo.arithmetic.algorithm.recursion;

import java.util.Arrays;

/**
 * 斐波那契数列
 */
public class Fibonacci {
    public static void main(String[] args) {
        long s = System.currentTimeMillis();
        System.out.println(fina(5));
        long s1 = System.currentTimeMillis();
        System.out.println(s1 - s);
        System.out.println(finaOptimized(40));
        long s2 = System.currentTimeMillis();
        System.out.println(s2 - s1);
    }

    /**
     * 时间复杂度高 指数级 1.618^n
     */
    public static int fina(int n) {
        if (n == 0 || n == 1) {
            return n;
        }

        return fina(n - 1) + fina(n - 2);
    }


    /**
     * 优化后的斐波那契数列算法
     * 剪枝法 备忘录
     */

    public static int finaOptimized(int n) {
        int[] cached = new int[n + 1];
        Arrays.fill(cached, -1);
        cached[0] = 0;
        cached[1] = 1;

        return fina2(n, cached);
    }


    public static int fina2(int n, int[] cached) {
        if (cached[n] != -1) {
            return cached[n];
        }
        int x = fina2(n - 1, cached);
        int y = fina2(n - 2, cached);
        cached[n] = x + y;
        return cached[n];
    }
}
